package leetcode;

/**
 * @author caifangyi
 * @date 2022/8/22
 */

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * 输出二叉树
 * 给你一棵二叉树的根节点 root ，请你构造一个下标从 0 开始、大小为 m x n 的字符串矩阵 res ，用以表示树的 格式化布局 。构造此格式化布局矩阵需要遵循以下规则：
 *
 * 树的 高度 为 height ，矩阵的行数 m 应该等于 height + 1 。
 * 矩阵的列数 n 应该等于 2height+1 - 1 。
 * 根节点 需要放置在 顶行 的 正中间 ，对应位置为 res[0][(n-1)/2] 。
 * 对于放置在矩阵中的每个节点，设对应位置为 res[r][c] ，将其左子节点放置在 res[r+1][c-2height-r-1] ，右子节点放置在 res[r+1][c+2height-r-1] 。
 * 继续这一过程，直到树中的所有节点都妥善放置。
 * 任意空单元格都应该包含空字符串 "" 。
 * 返回构造得到的矩阵 res 。
 *
 * 示例 1：
 *
 *
 * 输入：root = [1,2]
 * 输出：
 * [["","1",""],
 * ["2","",""]]
 * 示例 2：
 *
 *
 * 输入：root = [1,2,3,null,4]
 * 输出：
 * [["","","","1","","",""],
 * ["","2","","","","3",""],
 * ["","","4","","","",""]]
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/print-binary-tree
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Day0655 {

    public static void main(String[] args) {

    }


    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    class Solution {

        int m,n;
        List<List<String>> list = new ArrayList<>();
        int h=0;
        public List<List<String>> printTree(TreeNode node) {
            df1(node, 0);
            m = h+1;
            n = (int) (Math.pow(2, m) -1);
            for (int i = 0; i < m; i++) {
                List<String> mList = new ArrayList<>();
                for (int j = 0; j < n; j++) {
                    mList.add("");
                }
                list.add(mList);
            }

            df2(node, 0, (n-1)/2);
            return list;

        }

        private void df2(TreeNode node, int x, int y) {
            if(node == null){
                return;
            }
            list.get(x).set(y, String.valueOf(node.val));
            df2(node.left, x+1, (int) (y-Math.pow(2,h-x-1)));
            df2(node.right, x+1, (int) (y+Math.pow(2,h-x-1)));
        }

        private void df1(TreeNode node, int i) {
            if(node==null){
                return;
            }
            h = Math.max(h, i);
            ++i;
            df1(node.left, i);
            df1(node.right, i);
        }
    }

}
